package com.example.ureport2.demo.util;

import java.util.List;

/**
 * @author zero
 * @date 2019-04-28
 **/
public class DatasetUtil {

    private DatasetUtil() {
    }

    /**
     * 快速排序算法
     *
     * @param arr  需要排序的数组
     * @param low  开始时最左边的索引 = 0
     * @param high 开始时最右边的索引 = arr.length - 1
     */
    private static void quickSort(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }

        // 哨兵i
        int i = low;
        // 哨兵j
        int j = high;
        // 基准位
        int position = arr[low];

        while (i < j) {
            // 先看右边，依次往左递减
            while (position <= arr[j] && i < j) {
                j--;
            }

            // 再看左边，依次往右递增
            while (position >= arr[i] && i < j) {
                i++;
            }

            // 如果满足条件则交换
            if (i < j) {
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }

        // 最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = position;

        // 递归调用左半数组
        quickSort(arr, low, j - 1);
        // 递归调用右半数组
        quickSort(arr, j + 1, high);
    }

    /**
     * 排序
     *
     * @param arr 需要排序的数组
     */
    private static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 二分查找算法
     *
     * @param list 数据集
     * @param key  需要查找的元素
     * @return 查找到的元素下标
     */
    private static <T extends Comparable> int binarySearch(List<T> list, T key) {
        int low = 0;
        int high = list.size();

        while (low < high) {
            int mid = (low + high) >>> 1;
            @SuppressWarnings("unchecked")
            int result = key.compareTo(list.get(mid));

            if (result < 0) {
                high = mid;
            } else if (result > 0) {
                low = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }
}
